<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1737：[Usaco2005 jan]Naptime 午睡时间</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2005 jan]Naptime 午睡时间</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2005 jan]Naptime 午睡时间</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2005 jan]Naptime 午睡时间                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium">Goneril is a very sleep-deprived cow. Her day is partitioned into N (3 &lt;= N &lt;= 3,830) equal time periods but she can spend only B (2 &lt;= B &lt; N) not necessarily contiguous periods in bed. Due to her bovine hormone levels, each period has its own utility U_i (0 &lt;= U_i &lt;= 200,000), which is the amount of rest derived from sleeping during that period. These utility values are fixed and are independent of what Goneril chooses to do, including when she decides to be in bed. With the help of her alarm clock, she can choose exactly which periods to spend in bed and which periods to spend doing more critical items such as writing papers or watching baseball. However, she can only get in or out of bed on the boundaries of a period. She wants to choose her sleeping periods to maximize the sum of the utilities over the periods during which she is in bed. Unfortunately, every time she climbs in bed, she has to spend the first period falling asleep and gets no sleep utility from that period. The periods wrap around in a circle; if Goneril spends both periods N and 1 in bed, then she does get sleep utility out of period 1. What is the maximum total sleep utility Goneril can achieve? </span></p>
<div><span style="font-size: medium">贝茜是一只非常缺觉的奶牛．她的一天被平均分割成N段(3&le;N&le;3830)，但是她要用其中的B段时间(2&le;B&lt;&nbsp;N)睡觉．每段时间都有一个效用值Ui(0&le;Ui&le;200000)，只有当她睡觉的时候，才会发挥效用．&nbsp;&nbsp;&nbsp;&nbsp;有了闹钟的帮助，贝茜可以选择任意的时间入睡，当然，她只能在时间划分的边界处入睡、醒来．&nbsp;&nbsp;&nbsp;&nbsp;贝茜想使所有睡觉效用的总和最大．不幸的是，每一段睡眠的第一个时间阶段都是&ldquo;入睡&rdquo;阶段，而旦不记入效用值．&nbsp;&nbsp;&nbsp;&nbsp;时间阶段是不断循环的圆（一天一天是循环的嘛），假如贝茜在时间N和时间1睡觉，那么她将得到时间1的效用值．</span></div></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium">* Line 1: Two space-separated integers: N and B</span></p>
<p><span style="font-size: medium">* Lines 2..N+1: Line i+1 contains a single integer, U_i, between 0 and 200,000 inclusive </span></p>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;第1行：两个整数，N和B.</span></div>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;第2到N+1行：每行1个数字，代表了时间i的效用值．</span></div></p><hr/><h3>输出格式</h3><p><p><span style="font-size: medium">* Line 1: A single integer, the maximum total sleep utility Goneril can achieve. </span></p>
<div><span style="font-size: medium">&nbsp;&nbsp;&nbsp;&nbsp;最大的效用值．</span></div>
<p></p></p><hr/><h3>样例输入</h3><pre>5 3
2
0
3
1
4
</pre><hr/><h3>样例输出</h3><pre>6

选择时间段1（入睡），4，2</pre><hr/><h3>提示</h3><p><p>见国家队2005 Twb,ZgL作业</p></p><hr/><h3>题目来源</h3><p>Gold</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1737" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1737" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>